package offer;

import digui.tree.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cyt
 * @create 2020-05-26 15:40
 */
public class T28 {

    /**
     * [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
     * <p>
     * {1,2,5,3,4,6,7}
     * <p>
     * <p>
     * 首先得到根节点   1
     * <p>
     * 然后划分左右子树
     * <p>
     * 3 2 4 ， 6 5 7
     * <p>
     * 先遍历左子树
     * <p>
     * 1、得到根节点索引位置
     */
    private static Map<Integer, Integer> indexForInOrders = new HashMap<>();

    public static void main(String[] args) {


    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++) {
            indexForInOrders.put(in[i], i);
        }
        return dfs(pre, 0, pre.length - 1, 0);
    }

    static void postVis(TreeNode node) {
        /**
         *        1
         *   2         3
         *     4     5  8
         *  7       6
         *
         */
        if (node == null) return;
        postVis(node.left);
        postVis(node.right);
        System.out.println(node.val);
    }

    public static TreeNode dfs(int[] pre, int preL, int preR, int inL) {
        // 结束递归
        if (preL > preR)
            return null;
        // 根节点
        TreeNode root = new TreeNode(pre[preL]);
        // 左子树
        // 当前根节点 在中序遍历中的位置
        int inIndex = indexForInOrders.get(root.val);
        int left = inIndex - inL;
        root.left = dfs(pre, preL + 1, preL + left, inL);
        // 右子树
        root.right = dfs(pre, preL + left + 1, preR, inL + 1 + left);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
